package collections.tree;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinaryTreeImpl<T> implements BinaryTree<T> {

    private int size;
    private TreeElement root;


    @Override
    public void add(T value) {
        TreeElement newElem = new TreeElement<>(value);
        if (root == null) root = newElem;
        else insert(newElem, root);
        size++;
    }

    private void insert(TreeElement newElem, TreeElement root){
        newElem.setRootElem(root);
        if (root.hashCode() < newElem.hashCode()){
            if (root.getRightNode() == null) root.setRightNode(newElem);
            else insert(newElem, root.getRightNode());
        }
        else if (root.hashCode() >= newElem.hashCode()){
            if (root.getLeftNode() == null) root.setLeftNode(newElem);
            else insert(newElem, root.getLeftNode());
        }
    }

    @Override
    public boolean remove(T value) {
        if (root.equals(value)){
            rootRemove();
            size--;
            return true;
        }

        TreeElement forRemove = containedElem(root, new TreeElement<>(value));
        if (forRemove == null) return false;

        if (forRemove.hashCode() <= forRemove.getRootElem().hashCode()) {
            setLeftRootNode(forRemove);
        } else {
            setRightRootNode(forRemove);
        }
        size--;
        return true;
    }

    private void rootRemove() {
        if (root.getLeftNode() == null && root.getRightNode() == null){
            root = null;
        } else if (root.getLeftNode() != null && root.getRightNode() != null) {
            insert(root.getLeftNode(), root.getRightNode());
        } else if (root.getLeftNode() == null && root.getRightNode() != null){
            root = root.getRightNode();
            root.getRightNode().setRootElem(null);
        } else {
            root = root.getLeftNode();
            root.getLeftNode().setRootElem(null);
        }
    }

    private void setRightRootNode(TreeElement elem) {
        if (elem.getLeftNode() == null && elem.getRightNode() == null){
            elem.getRootElem().setRightNode(null);
        } else if (elem.getLeftNode() == null || elem.getRightNode() == null){
            if (elem.getLeftNode() == null) {
                elem.getRootElem().setRightNode(elem.getRightNode());
            } else {
                elem.getRootElem().setRightNode(elem.getLeftNode());
            }
        } else {
            elem.getLeftNode().setRootElem(elem.getRootElem());
            elem.getRootElem().setRightNode(elem.getLeftNode());
            insert(elem.getRightNode(), elem.getLeftNode());
        }
    }

    private void setLeftRootNode(TreeElement elem) {
        if (elem.getLeftNode() == null && elem.getRightNode() == null){
            elem.getRootElem().setLeftNode(null);
        } else if (elem.getLeftNode() == null || elem.getRightNode() == null){
            if (elem.getLeftNode() == null) {
                elem.getRootElem().setLeftNode(elem.getRightNode());
            } else {
                elem.getRootElem().setLeftNode(elem.getLeftNode());
            }
        } else {
            elem.getRightNode().setRootElem(elem.getRootElem());
            elem.getRootElem().setLeftNode(elem.getRightNode());
            insert(elem.getLeftNode(), elem.getRightNode());
        }
    }

    @Override
    public void removeAll() {
        size = 0;
        root = null;
    }

    @Override
    public boolean contains(T value) {
        TreeElement check = containedElem(root, new TreeElement<>(value));
        return check != null;
    }

    private TreeElement containedElem(TreeElement root, TreeElement looked){
        if (root == null) return null;

        if (root.equals(looked.getValue())) return root;

        if (root.getRightNode() !=  null &&
                root.hashCode() < looked.hashCode())
            return containedElem(root.getRightNode(), looked);

        if (root.getLeftNode() != null &&
                root.hashCode() > looked.hashCode())
            return containedElem(root.getLeftNode(), looked);

        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int height(){
        return calculateHeight(root);
    }

    private int calculateHeight (TreeElement root){
        if (root == null) return 0;
        return 1+Math.max (calculateHeight(root.getLeftNode()),
                            calculateHeight(root.getRightNode()));
    }

    private void printWhitespaces(int count) {
        for (int i = count; i > 0; i--)
            System.out.print(" ");
    }

    @Override
    public void printTreeHorizontal(){
        horizontalPrintTree(root, 1);
    }

    private void horizontalPrintTree(TreeElement root, int height){
        if (root != null){
            horizontalPrintTree(root.getRightNode(), height+5);
            printWhitespaces(height);
            System.out.println(root);
            horizontalPrintTree(root.getLeftNode(), height+5);
        }
    }

    @Override
    public void printTreeVertical() {
        verticalPrintTree(Collections.singletonList(root), 1);
    }

    private void verticalPrintTree(List<TreeElement> nodes, int level) {
        if (nodes.isEmpty() || isAllElementsNull(nodes))
            return;

        int floor = height() - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        printWhitespaces(firstSpaces);

        List<TreeElement> newNodes = new ArrayList<>();
        for (TreeElement elem : nodes) {
            if (elem != null) {
                System.out.print(elem);
                newNodes.add(elem.getLeftNode());
                newNodes.add(elem.getRightNode());
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (TreeElement elem : nodes) {
                printWhitespaces(firstSpaces - i);
                if (elem == null) {
                    printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (elem.getLeftNode() != null)
                    System.out.print("/");
                else
                    printWhitespaces(1);

                printWhitespaces(i + i - 1);

                if (elem.getRightNode() != null)
                    System.out.print("\\");
                else
                    printWhitespaces(1);

                printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        verticalPrintTree(newNodes, level + 1);
    }

    private boolean isAllElementsNull(List list) {
        for (Object obj : list) {
            if (obj != null)
                return false;
        }
        return true;
    }
}
